import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer 58 - I. 翻转单词顺序
 * @author: WXY
 * @create: 2022-12-10 21:27
 * @Version 1.0
 **/


public class Num058_1_reverseWords {
    public static String reverseWords(String s) {
        char[] str = s.toCharArray();
        int l = 0;
        int r = str.length - 1;
        swapWords(str, l, r);
        swap(str);
        return qukongge(str);
    }

    private static String qukongge(char[] str) {
        int i = 0;
        int j = 0;
        int n = str.length;
        while (j < n) {
            while (j < n && str[j] == ' ') j++;
            while (j < n && str[j] != ' ') str[i++] = str[j++];
            while (j < n && str[j] == ' ') j++;
            if (j < n) str[i++] = ' ';
        }
        return new String(str).substring(0, i);
    }

    private static void swap(char[] str) {
        int start = 0;
        int end = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') {
                end = i - 1;
                swapWords(str, start, end);
                start = i + 1;
            }
        }
        end = str.length - 1;
        swapWords(str, start, end);
    }

    private static void swapWords(char[] str, int l, int r) {
        while (l < r) {
            char ch = str[l];
            str[l] = str[r];
            str[r] = ch;
            l++;
            r--;
        }
    }


    public static String reverseWords1(String s) {
        if (s.length() == 0) {
            return "";
        }
        Stack<String> stack = new Stack<>();
        String str = "";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                if (str.length() > 0) {
                    stack.push(str);
                    str = "";
                }
            } else {
                str += s.charAt(i);
            }
        }
        if (str.length() > 0) {
            stack.push(str);
        }
        String ans = "";
        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                ans += stack.pop() + " ";
            }
            return ans.substring(0, ans.length() - 1);
        } else {
            return "";
        }
    }


    public static void main(String[] args) {
        String str = reverseWords1("  ");
        System.out.println(str);
    }
}
